CIA hive CRC16算法简述与C,python实现

简介

在维基解密Vault 8: Hive中泄露了Hive的git目录，可通过git checkout ./ 获得代码

在触发包中使用CRC-16/CCITT-FALSE算法（CRC16的算法还是挺多的，这个网站可以计算9种CRC-16的值，我们可以通过这个网站可确认具体的CRC16算法的类型，我便是从这个网站确认的）

CRC-16/CCITT-FALSE算法步骤：
首先定义了两个16大小的表，用于查表，一个用于高8位，一个用于低8位
初始的CRC16_High和CRC16_Low都是0xff（这应该也是这算法称为False的原因）
接下来便是对每一个字节进行循环操作

1. 明文的高四位和CRC16_High的高四位进行异或，作为查表的索引
2. 之后CRC16_High的低4位和CRC16_Low的高四位进行或云锁重新组成新的CRC16_High；CRC16_Low则是直接将原来的CRC16_Low左移四位即可
3. 最后将CRC16_High和CRC16_Low分别异或查表结果即可
4. 而对于明文低四位的操作也是跟高四位的一样
5. 最后循环结束后，将CRC16_High跟CRC16_Low拼接起来就好了

C++实现

一开始从哪里抠出来的代码要添加头文件才能运行

#include <stdio.h>
#include <stdint.h>

uint16_t tiny_crc16(const uint8_t * msg, uint32_t sz);

int main(){

	char* msg = (char *)"\x01\xc5\x6c\x34\x8a\x3f\x75\xc7\xec\xd5\xe9\x80\x7d\x88\x6a\x6c\xb9\x47\x0e\xb3\x1a\x5d\x40\xf6\x61\xc7\x74\x25\x45\xd9\xa5\x46\x9e\x12\x7a\x28\x51\xf0\xef\x3e\xc5\xd8\xbe\x42\x61\x28\xaf\x1a\x6f\xbd\xcd\x89\x1a\x0d\x80\x7c\xd4\xf4\xa1\x1a\xcd\x47\x60\x6b\x59\xdb\x94\xaa\xcb\x83\xe8\x90\x5c\xa6\xd3\xbd\xce\x82\xd7\x3d\x3f\xa5\xc7\x5a";

	printf("%x\n", tiny_crc16((unsigned char *)msg, 84));

return 0;

}

uint16_t tiny_crc16(const uint8_t * msg, uint32_t sz){

	uint32_t index;
	uint16_t crc;
	uint8_t val, t;

	/*
	* CRC16 Lookup tables (High and Low Byte) for 4 bits per iteration.
	*/
	unsigned short CRC16_LookupHigh[16] = {
		0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70,
		0x81, 0x91, 0xA1, 0xB1, 0xC1, 0xD1, 0xE1, 0xF1
	};
	unsigned short CRC16_LookupLow[16] = {
		0x00, 0x21, 0x42, 0x63, 0x84, 0xA5, 0xC6, 0xE7,
		0x08, 0x29, 0x4A, 0x6B, 0x8C, 0xAD, 0xCE, 0xEF
	};

	/*
	* CRC16 "Register". This is implemented as two 8bit values
	*/
	unsigned char CRC16_High, CRC16_Low;
	// Initialise the CRC to 0xFFFF for the CCITT specification
	CRC16_High = 0xFF;
	CRC16_Low = 0xFF;

	for (index = 0; index < sz; index++){

		val = msg[index] >> 4;

		// Step one, extract the Most significant 4 bits of the CRC register
		t = CRC16_High >> 4;

		// XOR in the Message Data into the extracted bits
		t = t ^ val; //高四位进行异或

		// Shift the CRC Register left 4 bits
		CRC16_High = (CRC16_High << 4) | (CRC16_Low >> 4);  // high的低4位和low的高四位重新组成新的high
		CRC16_Low = CRC16_Low << 4; //新的低四位则直接左移四位

		// 根据上面高四位的异或结果进行查表
		// Do the table lookups and XOR the result into the CRC Tables
		CRC16_High = CRC16_High ^ CRC16_LookupHigh[t];
		CRC16_Low = CRC16_Low ^ CRC16_LookupLow[t];


		val = msg[index] & 0x0F; //取低四位

		// Step one, extract the Most significant 4 bits of the CRC register
		t = CRC16_High >> 4;

		// XOR in the Message Data into the extracted bits
		t = t ^ val;

		// Shift the CRC Register left 4 bits
		CRC16_High = (CRC16_High << 4) | (CRC16_Low >> 4);
		CRC16_Low = CRC16_Low << 4;

		// 根据上面低四位的异或结果进行查表
		// Do the table lookups and XOR the result into the CRC Tables
		CRC16_High = CRC16_High ^ CRC16_LookupHigh[t];
		CRC16_Low = CRC16_Low ^ CRC16_LookupLow[t];
	}
	// 最后High左移8位跟Low进行异或
	crc = CRC16_High;  
	crc = crc << 8;
	crc = crc ^ CRC16_Low;

	return crc;
}

python实现

# -*-coding:utf-8-*-
# 算法：CRC-16/CCITT-FALSE

def crc16(msg):

    CRC16_LookupHigh = [0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70,
        0x81, 0x91, 0xA1, 0xB1, 0xC1, 0xD1, 0xE1, 0xF1]
    CRC16_LookupLow = [0x00, 0x21, 0x42, 0x63, 0x84, 0xA5, 0xC6, 0xE7,
        0x08, 0x29, 0x4A, 0x6B, 0x8C, 0xAD, 0xCE, 0xEF]

    CRC16_High = 0xFF
    CRC16_Low = 0xFF

    for i in xrange(0, len(msg)):
        # 利用高四位计算索引值
        val = ord(msg[i]) >> 4
        t = CRC16_High >> 4
        t = t ^ val

        CRC16_High = ((CRC16_High << 4) | (CRC16_Low >> 4)) & 0xff
        CRC16_Low = (CRC16_Low << 4) & 0xff

        CRC16_High = CRC16_High ^ CRC16_LookupHigh[t];
        CRC16_Low = CRC16_Low ^ CRC16_LookupLow[t];

        # 利用低四位计算索引值
        val = ord(msg[i]) & 0xF
        t = CRC16_High >> 4;
        t = t ^ val;

        CRC16_High = ((CRC16_High << 4) | (CRC16_Low >> 4)) & 0xff
        CRC16_Low = (CRC16_Low << 4) & 0xff

        CRC16_High = CRC16_High ^ CRC16_LookupHigh[t];
        CRC16_Low = CRC16_Low ^ CRC16_LookupLow[t];

    crc = (CRC16_High << 8) ^ CRC16_Low
    return hex(crc)

print crc16("\x01\xc5\x6c\x34\x8a\x3f\x75\xc7\xec\xd5\xe9\x80\x7d\x88\x6a\x6c\xb9\x47\x0e\xb3\x1a\x5d\x40\xf6\x61\xc7\x74\x25\x45\xd9\xa5\x46\x9e\x12\x7a\x28\x51\xf0\xef\x3e\xc5\xd8\xbe\x42\x61\x28\xaf\x1a\x6f\xbd\xcd\x89\x1a\x0d\x80\x7c\xd4\xf4\xa1\x1a\xcd\x47\x60\x6b\x59\xdb\x94\xaa\xcb\x83\xe8\x90\x5c\xa6\xd3\xbd\xce\x82\xd7\x3d\x3f\xa5\xc7\x5a")

python 库

雨村后来找到一个crc的库，kali安装有点问题，建议使用ubuntu
https://pycrc.readthedocs.io/en/latest/usage.html

下面的示例代码那个0xffff正是CRC16_High，CRC16_Low结合起来的一个初始值

>>> from PyCRC.CRCCCITT import CRCCCITT
>>> input = b'\x05d\x05\xc0\x00\x01\x00\x0c'
>>> print(hex(CRCCCITT("FFFF").calculate(input)))
0x8d59'\x05d\x05\xc0\x00\x01\x00\x0c'
print(hex(CRCCCITT("FFFF").calculate(input)))